Andrew Goldberg, Microsoft Research
Abstract:
This is a survey of Hub Labeling results for general and road networks.
Given a weighted graph, a distance oracle takes as an input a pair of vertices and returns the distance between them. The labeling approach to distance oracle
design is to precompute a label for every vertex so that distances can be computed from the corresponding labels. This approach has been introduced by
[Gavoille et al. '01], who also introduced the Hub Labeling algorithm (HL). HL has been further studied by [Cohen et al. '02].
We study HL in the context of graphs with small highway dimension (e.g., road networks). We show that under this assumption HL labels are
small and the queries are sublinear. We also give an approximation algorithm for computing small HL labels that uses the fact that shortest path set
systems have small VC-dimension.
Although polynomial-time, precomputation given by theory is too slow for continental-size road networks. However, heuristics guided by the theory are
fast, and compute very small labels. This leads to the fastest currently known practical distance oracles for road networks.
The simplicity of HL queries allows their implementation inside of a relational database (e.g., in SQL), and query efficiency assures real-time response.
Furthermore, including HL data in the database allows efficient implementation of more sophisticated location-based queries. These queries can be combined
with traditional SQL queries. This approach brings the power of location-based services to SQL programmers, and benefits from external memory implementation
and query optimization provided by the underlying database.
Joint work with Ittai Abraham, Daniel Delling, Amos Fiat, and Renato Werneck